package Leetcode.网格图;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: kirito
 * @Date: 2024/5/5 14:07
 * @Description:
 * 矩阵中移动的最大次数
 * 已解答
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。
 *
 * 你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：
 *
 * 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。
 * 返回你在矩阵中能够 移动 的 最大 次数。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
 * 输出：3
 * 解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
 * - (0, 0) -> (0, 1).
 * - (0, 1) -> (1, 2).
 * - (1, 2) -> (2, 3).
 * 可以证明这是能够移动的最大次数。
 * 示例 2：
 *
 *
 * 输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
 * 输出：0
 * 解释：从第一列的任一单元格开始都无法移动。
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 2 <= m, n <= 1000
 * 4 <= m * n <= 105
 * 1 <= grid[i][j] <= 106
 */

public class maxMoves {
    /**
     * 我们首先把所有行坐标加入到集合中，作为出发点。然后对其依次遍历，对每一个单元格，
     * 找到下一个列的相邻单元格，并判断是否严格大于当前单元格。
     * 如果是，说明可以移动到达。把所有可到达的单元格行坐标加到集合中，并用于下一轮的搜索。
     *
     * 当到达最后一列或者集合为空，搜索结束，返回矩阵中移动的最大次数。
     * @param grid
     * @return
     */
    public int maxMoves(int[][] grid) {
        // 获取矩阵的长度和宽度
        int m = grid.length; // 行数
        int n = grid[0].length; // 列数

        // 使用HashSet来存储可达到的行索引，初始时所有行都是可达的
        Set<Integer> q = new HashSet<>();
        for (int i = 0; i < m; i++) {
            q.add(i);
        }

        // 遍历每一列，从第二列开始，因为第一列没有前一行可以比较
        for (int j = 1; j < n; j++) {
            // 创建一个新的HashSet来存储新的可达行索引
            Set<Integer> q2 = new HashSet<>();

            // 遍历当前列中所有可达的行索引
            for (int i : q) {
                // 检查当前行的每个相邻行（上、下、左、右）
                for (int i2 = i - 1; i2 <= i + 1; i2++) {
                    // 如果相邻行在矩阵范围内，并且相邻行的值大于当前行的值
                    if (0 <= i2 && i2 < m && grid[i][j - 1] < grid[i2][j]) {
                        // 将相邻行索引添加到新的HashSet中
                        q2.add(i2);
                    }
                }
            }
            // 用新的可达行索引更新旧的HashSet
            q = q2;

            // 如果当前列没有可达的行，返回当前列数减一
            if (q.isEmpty()) {
                return j - 1;
            }
        }

        // 遍历结束，返回最后一列的索引
        return n - 1;
    }


    private int ans;

    public int maxMoves2(int[][] grid) {
        // 初始化最大移动次数为0
        ans = 0;

        // 遍历矩阵的每一行
        for (int i = 0; i < grid.length; i++) {
            // 从每一行的任意位置开始进行深度优先搜索
            dfs(i, 0, grid);
        }

        // 返回计算出的最大移动次数
        return ans;
    }

    private void dfs(int i, int j, int[][] grid) {
        // 更新当前移动次数，以当前列索引表示
        ans = Math.max(ans, j);

        // 如果已经达到最大列索引，即到达最后一列，则返回
        if (ans == grid[0].length - 1) {
            return;
        }

        // 尝试向右上、右、右下方向移动
        for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, grid.length); k++) {
            // 如果下一个单元格的值大于当前单元格的值，则可以移动
            if (grid[k][j + 1] > grid[i][j]) {
                // 递归地进行深度优先搜索
                dfs(k, j + 1, grid);
            }
        }

        // 将当前单元格标记为已访问，防止重复访问
        grid[i][j] = 0;
    }

}
